1. Field of the Invention
The present invention relates generally to the field of computer systems. More particularly, the present invention relates to the field of random number generators for use by computer systems.
2. Description of Related Art
Random number generators may be used for a variety of electronic applications, such as lotteries, gambling machines, video games, image processing and reconstruction, music and graphics composition, scientific and financial modeling simulation, program and algorithm testing, equation-solving, and computer security for example. For computer security applications such as cryptography, digital signatures, and protected communication protocols, for example, random numbers are a fundamental building block for strengthening and securing the confidentiality of electronic communications.
Random numbers are a sequence of independent numbers with a specified distribution and a specified probability of falling in any given range of values. An ideal random number generator provides a stream of uniformly distributed, non-deterministic, independent bits over an infinite data.
Random number generators generate and output random bits each with some amount of entropy or randomness depending on how the random bits are generated. A single bit can have anywhere between zero entropy, that is the single bit has a fully predictable value, and full entropy, that is the single bit has a fully unpredictable value, depending on the quality of the random number generation scheme used to generate the single bit. For typical random number generators, transient perturbations, such as injected noise or periodic phase correlation between oscillators in the random number generator for example, can reduce the entropy of generated random bits.
To compensate for such reduced entropy, typical random number generators inject the generated random bits into an entropy accumulator. One typical entropy accumulator is known as a linear feedback shift register (LFSR) and comprises a series of latches with an output random bit flowing back to the input of the LFSR. Each random bit input to the LFSR is typically exclusive-ORed with the random bit being output from the last latch in the LFSR, with the exclusive-OR result being input to the first latch in the LFSR. One or more random bits output from the first or an intermediate latch may also be exclusive-ORed with the random bit being output from the last latch in the LFSR, with the exclusive-OR result being input to the next latch in the LFSR. As a result, the random bits output from the LFSR have an entropy approximating the average entropy injected into the LFSR. The LFSR therefore effectively filters out instantaneous reductions of entropy.
The random bit output from the last latch in the LFSR, however, is also output by the random number generator and therefore becomes known. That random bit therefore has zero entropy with respect to the random bits not yet output and therefore does not contribute to the entropy added to the first latch through the first exclusive-OR operation. Because the amount of entropy output by the LFSR can exceed the amount of entropy injected into the LFSR and because the LFSR state can be derived by reading n bits of output, where n is the number of latches in the LFSR, propagating random bits through an LFSR in this manner offers relatively minimal entropy accumulation.